/* 
  使用堆实现一个优先级队列
 */

class PriorityQueue {
  constructor() {
    this.heap = new MaxHeap();
  }

  getSize() {
    return this.heap.getSize();
  }
  isEmpty() {
    return this.heap.isEmpty();
  }
  enqueue(data) {
    this.heap.add(data);
  }
  dequeue() {
    return this.heap.getMax();
  }
  peek() {
    return this.heap.findMax();
  }
}

/* 
  1 实现一个最大堆
  2 堆的两个性质
    1 堆时一个完全二叉树，即只有最后一层的元素才有可能是不满的，其他层都是满的
    2 堆中的节点一定大于其左右孩子的值
*/

class MaxHeap {
  constructor(arr, compare) {
    this.arr = [];
    this.compare = compare || ((a, b) => a - b);
    // 使用一个数组存值
    if (arr) {
      this.heapify(arr);
    }
  }

  getSize() {
    return this.arr.length;
  }

  isEmpty() {
    return this.getSize() === 0;
  }

  parent(index) {
    return Math.floor((index - 1) / 2);
  }
  leftChild(index) {
    return Math.floor(index * 2 + 1);
  }
  rightChild(index) {
    return Math.floor(index * 2 + 2);
  }
  swap(i, j) {
    const temp = this.arr[i];
    this.arr[i] = this.arr[j];
    this.arr[j] = temp;
  }
  // 添加一个元素
  add(data) {
    this.arr.push(data);
    this.siftUp(this.arr.length - 1);
  }
  siftUp(k) {
    while (k > 0 && this.compare(this.arr[k], this.arr[this.parent(k)]) > 0) {
      // 大于父节点的值，上浮
      this.swap(k, this.parent(k));
      k = this.parent(k);
    }
  }

  findMax() {
    if (this.getSize() === 0) {
      throw new Error('heap is empty!');
    }
    return this.arr[0];
  }

  getMax() {
    const max = this.findMax();
    this.swap(0, this.getSize() - 1);
    this.arr.pop();
    this.siftDown(0);
    return max;
  }
  siftDown(k) {
    while (k < this.getSize() && this.leftChild(k) < this.getSize()) {
      let j = this.leftChild(k);
      if (
        j + 1 < this.getSize() &&
        this.compare(this.arr[j + 1], this.arr[j]) > 0
      ) {
        j = this.rightChild(k);
      }
      if (this.compare(this.arr[k], this.arr[j]) >= 0) {
        break;
      }
      this.swap(k, j);
      k = j;
    }
  }

  // 返回堆顶元素(也就是最大元素)，在插入一个新的元素
  replace(data) {
    const res = this.findMax();
    this.arr[0] = data;
    this.siftDown(0);
    return res;
  }

  // heapify（堆化，也就是给定一个数组，把它变成一个最大堆的形式）
  heapify(arr) {
    // 原理：
    /*
      分析可以发现：
        1 堆的叶子节点是不需要排序的，也就是siftDown操作
        2 只有堆的非叶子节点需要siftDown操作
      总结：从堆中的倒数第一个非叶子节点逆序开始siftDown操作，即可完成堆化 
      最后一个非叶子节点的索引就是：最后一个叶子节点的父节点
     */
    if (!arr || arr.length <= 1) {
      return;
    }
    for (let i = this.parent(arr.length - 1); i >= 0; i--) {
      this.siftDown(i);
    }
  }
}

/** 使用优先级队列完成这个问题
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  /* 
    1 
  */
  const result = [];
  const queue = new PriorityQueue();
  if (!nums || nums.lenght === 0) {
    return result;
  }
  for (let i = 0; i < nums.length; i++) {
    if (queue.getSize() === k) {
      // 取出最大元素
      result.push(queue.peek());
      queue.enqueue(nums[i])
    }
    // 在放入新的元素
    queue.enqueue(nums[i]);
  }
  return result;
};

console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
var smallestK = function (arr, k) {
  const result = [];
  const queue = new PriorityQueue();
  for (let i = 0; i < k; i++) {
    // console.log(11);
    queue.enqueue(arr[i]);
  }
  for (let j = k; j < arr.length; j++) {
    // console.log(22);
    if (!queue.isEmpty() && arr[j] < queue.peek()) {
      // 说明是小的值，入队
      queue.dequeue();
      queue.enqueue(arr[j]);
    }
  }
  /*  while (!queue.isEmpty()) {
    result.push(queue.dequeue());
  } */
  for (let i = 0; i < k; i++) {
    // console.log(233);
    result.push(queue.dequeue());
  }
  return result;
};

// smallestK([1, 3, 4, 7, 8, 9], 3);
